AGC026E Synchronized Subsequence <贪心+DP>

Problem

Synchronized Subsequence

Statement

You are given a string of length , containing occurrences of a and occurrences of b.
You will choose some of the characters in . Here, for each , it is not allowed to choose exactly one of the following two: the occurrence of a and the occurrence of b. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).
Find the lexicographically largest string that can be obtained in this way.

Constraints

is a string of length containing occurrences of a and occurrences of b.

Input

Input is given from Standard Input in the following format:

Output

Print the lexicographically largest string that satisfies the condition.

Sample

Input #1

1
2

3
aababb

Output #1

abab

Explanation #1
A subsequence of obtained from taking the first, third, fourth and sixth characters in , satisfies the condition.
Input #2

1
2

3
bbabaa

Output #2

bbabaa

Explanation #2
You can choose all the characters.
Input #3

1 2	6 bbbaabbabaaa

Output #3

bbbabaaa

Input #4

1 2	9 abbbaababaababbaba

Output #4

1	bbaababababa

标签：贪心 DP

Translation

给出一个长为的仅由a和b组成的字符串，每次可以删除第个a和第个b。求最终形成的字典序最大的串。

Solution

首先将整个串分为若干段，每一段都保证a的个数和b的个数相等。
设第对a,b的位置分别为，那么每一段中满足以下两种条件之一：

对于，显然最后的串是abab...的形式，于是直接贪心从前往后选，对于当前这一对如果a的位置在上一次选的的b的位置之后，即可选当前这一对。
对于，如果选了中间的某一组，则其后面的都选一定比不选要优。于是枚举哪一组开始选，贪心求出字典序最大的串。
如此，可以将每一段都处理成能变成的字典序最大的串。最后需要考虑的就是拼起来。
显然，对于某一段，只有选和不选两种可能，于是用表示选第段做开头，后面的串可以任意选，能得到的字典序最大的串（这里是一个数组）。那么。这样可以做。最后的答案为。

附上官方题解

Code

#include <bits/stdc++.h>
#define MAX_N 3000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
vector <string> S;
string s, f[MAX_N+5];
string sol() {
    vector <int> a, b, id, p;
    for (int i = 0; i < (int)s.size(); i++)
        if (s[i] == 'a') a.push_back(i);
        else b.push_back(i);
    for (int i = 0, pa = 0, pb = 0; i < (int)s.size(); i++)
        if (s[i] == 'a') id.push_back(pa), p.push_back(b[pa]), pa++;
        else id.push_back(pb), p.push_back(a[pb]), pb++;
    string ret = "";
    if (s[0] == 'a') {
        for (int i = 0; i < (int)s.size(); i++)
            if (s[i] == 'a') ret += "ab", i = p[i];
    } else {
        for (int i = (int)id.size()-1; ~i; i--) {
            string ss = "";
            for (int j = 0; j < (int)s.size(); j++)
                if (id[j] >= i) ss.push_back(s[j]);
            ret = max(ret, ss);
        }
    }
    return ret;
}
int main() {
    int n; read(n); string str; cin >> str, s = "";
    for (int i = 0, cnt = 0; i < (int)str.size(); i++) {
        s.push_back(str[i]), cnt += str[i] == 'a' ? 1 : -1;
        if (!cnt) S.push_back(sol()), s.clear();
    }
    string ans = "";
    for (int i = (int)S.size()-1; ~i; i--) {
        f[i] = S[i];
        for (int j = i+1; j < (int)S.size(); j++)
            f[i] = max(f[i], S[i]+f[j]);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}